Hashing হল একটি প্রক্রিয়া যা ডেটাকে একটি নির্দিষ্ট আকারের হ্যাশ কোডে রূপান্তরিত করে। এটি ডেটা দ্রুত অনুসন্ধান, সঞ্চয় এবং অ্যাক্সেস করার জন্য ব্যবহৃত হয়। hashing মূলত ডেটা স্ট্রাকচার তৈরির জন্য ব্যবহৃত হয়, যা হ্যাশ টেবিল নামে পরিচিত।
১. হ্যাশ ফাংশন
হ্যাশ ফাংশন হল একটি অ্যালগরিদম যা একটি ইনপুট কী (key) থেকে একটি হ্যাশ কোড উৎপন্ন করে। এই হ্যাশ কোডটি একটি সংখ্যা বা সূচক হিসেবে কাজ করে, যা ইনপুট কী দ্বারা প্রদত্ত মানের অবস্থান নির্দেশ করে।
১.১ হ্যাশ ফাংশনের কাজ
- প্রবেশাধিকার: হ্যাশ ফাংশন একটি কী থেকে একটি নির্দিষ্ট আকারের হ্যাশ কোড তৈরি করে, যা ডেটা দ্রুত অ্যাক্সেস করতে সহায়ক।
- সমান বিতরণ: একটি ভাল হ্যাশ ফাংশন কীগুলিকে সঠিকভাবে বিতরণ করে, যাতে একই হ্যাশ কোড পাওয়ার সম্ভাবনা কম হয়।
১.২ হ্যাশ ফাংশনের উদাহরণ
unsigned int hash(const char *key) {
unsigned int hash = 0;
while (*key) {
hash = (hash << 5) + *key++; // Shift left and add current character
}
return hash % TABLE_SIZE; // Return index
}
২. হ্যাশ টেবিল
হ্যাশ টেবিল হল একটি ডেটা স্ট্রাকচার যা কী-ভ্যালু জোড়া ধারণ করে। হ্যাশ টেবিলের মাধ্যমে, ডেটাকে একটি ইনডেক্সে সংরক্ষণ করা হয়, যা হ্যাশ ফাংশনের মাধ্যমে তৈরি হয়।
২.১ হ্যাশ টেবিলের গঠন
- কী (Key): একটি ইউনিক শনাক্তকারী যা মানের সাথে যুক্ত থাকে।
- মান (Value): কী দ্বারা সংরক্ষিত তথ্য।
২.২ সংঘর্ষ (Collision)
সংঘর্ষ ঘটে যখন দুটি ভিন্ন কী একই হ্যাশ কোড তৈরি করে। সংঘর্ষ মোকাবেলা করার জন্য বিভিন্ন পদ্ধতি রয়েছে, যেমন:
- চেইনিং: প্রতিটি ইনডেক্সে একটি লিঙ্কড লিস্ট তৈরি করা, যাতে একাধিক কী একই ইনডেক্সে সংরক্ষিত হতে পারে।
- অ্যাড্রেসিং: হ্যাশ টেবিলে উপস্থিত অব্যবহৃত ইনডেক্সে কী সন্নিবেশ করা।
৩. হ্যাশিং এর সুবিধা
- দ্রুত অনুসন্ধান: হ্যাশিং ব্যবহার করে, ডেটা দ্রুত অনুসন্ধান করা যায়, সাধারণত O(1) সময় জটিলতায়।
- সংরক্ষণের সুবিধা: কী-ভ্যালু জোড়া ব্যবহার করে ডেটা সঞ্চয় এবং অ্যাক্সেস করা সহজ হয়।
- বিপুল ডেটা: বড় ডেটা সেটের মধ্যে দ্রুত তথ্য খোঁজার জন্য কার্যকরী।
৪. হ্যাশিং এর অসুবিধা
- সংঘর্ষের সমস্যা: সংঘর্ষ ঘটলে এটি কার্যকারিতা কমাতে পারে, এবং সঠিকভাবে মোকাবেলা করা জরুরি।
- স্থান ব্যবস্থাপনা: বড় ডেটা সেটের জন্য, হ্যাশ টেবিলের আকার বাড়ানো প্রয়োজন হতে পারে, যা কার্যকারিতা হ্রাস করে।
Content added By
Read more
